#ifndef _HEAPSORT_H
#define _HEAPSORT_H

#include <cassert>
#include <iostream>
#include <math.h>
#include <stdlib.h>

using namespace std;

#define LEFT(i) (2*i)
#define RIGHT(i) (2*i+1)
#define PARENT(i) (i/2)


template <typename T>
void heap_print(T seq[],int n)
{
    int h=floor(log(double(n))/log(2.))+1;
    for(int i=1;i<=h;i++)
    {
        for(int j=0;j<h-i;j++)
            cout<<"\t";
        for(int j=pow(2.,i-1);j<pow(2.,i) && j<n;j++)
            cout<<seq[j-1]<<"\t";
        cout<<endl;
    }
}

template <typename T>
void heap_maxify(T seq[],int n,int index)
{
    assert(index<=n);
    int leftindex=LEFT(index);
    int rightindex=RIGHT(index);
    int largestone=index;
    if(leftindex<=n && seq[leftindex-1]>seq[largestone-1])
        largestone=leftindex;
    if(rightindex<=n && seq[rightindex-1]>seq[largestone-1])
        largestone=rightindex;
    if(largestone!=index)
    {
        T temp=seq[index-1];
        seq[index-1]=seq[largestone-1];
        seq[largestone-1]=temp;
        heap_maxify(seq,n,largestone);
    }
}

template <typename T>
void heap_create(T seq[],int n)
{
    int partion=n/2;
    for(int i=partion;i>=1;i--)
        heap_maxify(seq,n,i);
}

template <typename T>
void heap_sort(T seq[],int n)
{
    heap_create(seq,n);
    for(int i=n;i>=2;i--)
    {
        T temp=seq[i-1];
        seq[i-1]=seq[0];
        seq[0]=temp;
        heap_maxify(seq,i-1,1);
    }
}


#endif